
#include <cstdio>
#include <iostream>
//#include "library2.h"

template <class T>
class DynamicArray{
public:
	T** array;
	int size;
public:
	int current;

	DynamicArray <T>(int N):
		array(new T*[N]), size(N), current(0){
			for(int i=0; i<N; i++){
				array[i]=NULL;
			}
		}

	~DynamicArray <T>(){
		delete[] array;
	}
	int insert(T* ptr){
		if(current<size){
					array[current]=ptr;
					return current++;
			}
		T** newArray(new T* [2*size]);
		for(int i =0; i<size; i++){
			newArray[i]=array[i];
			newArray[i+size]=NULL;
		}
		delete[] array;
		newArray[current]=ptr;
		array=newArray;
		size=2*size;
		return ++current;
		}

	void edit(int i, T* ptr){
		if(i>=current){
			return;
		}
		array[i]=ptr;
	}


		T* operator[](int i) {
		if(i<size){
					return array[i];
			}
		return NULL;
		}
};


//*********************Errors*******************************
typedef enum {
	SUCCESS = 0,
	FAILURE = -1,
	ALLOCATION_ERROR = -2,
	INVALID_INPUT = -3
} StatusType;


//************************Tower*********************************

//************************Cube*********************************
typedef struct Cube{
	int _width;
	int _length;
	int _parent;
	int _position;
	int _tower;
	int _relativeHight;
};

class Tower{
private:
public:
	int _size;
	Cube* _base;
	Cube* _top;
	Cube* _root;

public:
	Tower(Cube* cube):
		_size(1), _base(cube), _top(cube), _root(cube){}
	Tower(int size, Cube* base,Cube* top,Cube* root):
		_size(size),_base(base),_top(top),_root(root){}
};

class Lego{
public:
	DynamicArray <Cube> _pieces;
	DynamicArray <Tower> _towers;

	int find(int N, int* height) {
		if(!_pieces[N]){
			return -1;
		}
		if(_pieces[N]->_parent==-1){
			if(height!=NULL) *height=_pieces[N]->_relativeHight;
				return _pieces[N]->_tower;
		}
		if(_pieces[_pieces[N]->_parent]->_parent!=-1){
			Cube* cube=_pieces[N];
			int sum=0;
			while(cube->_parent!=-1){
				sum+=cube->_relativeHight;
				cube=_pieces[cube->_parent];
			}
			Cube* root=cube;
			cube=_pieces[N];
			Cube* next=_pieces[cube->_parent];
			while(next->_parent!=-1){
				sum-=cube->_relativeHight;
				cube->_relativeHight+=sum;
				cube->_parent=root->_position;
				cube=next;
				next=_pieces[next->_parent];
			}
		}
			if(height!=NULL)*height=_pieces[N]->_relativeHight + _pieces[_pieces[N]->_parent]->_relativeHight;
			return _pieces[_pieces[N]->_parent]->_tower;
	}
public:
	Lego(): _pieces(10), _towers(10){}
	~Lego(){
		for(int i=0; i<_towers.current; i++){
			delete _towers[i];
		}
		for(int i=0; i<_pieces.current; i++){
			delete _pieces[i];
		}
	}

		StatusType addCube(int length, int width){
		if(length<1 || width<1) return FAILURE;
		Cube temp = {width, length, -1, -1, -1, 0};
		Cube* newCube=new Cube;
		*newCube= temp;
		Tower* newTower=new Tower(newCube);
		newCube->_tower=_towers.insert(newTower);
		newCube->_position = _pieces.insert(newCube);
		return SUCCESS;

	}
	StatusType putOnTop(int cubeUp,int cubeDown){
		if(cubeUp<0 || cubeDown<0){
			return INVALID_INPUT;
		}
		int towerUp = find(cubeUp,NULL);
		int towerDown = find(cubeDown,NULL);
		if(towerUp==-1 || towerDown==-1 || towerDown==towerUp){
			return FAILURE;
		}
		int downLength = _towers[towerDown]->_top->_length;
		int downWidth = _towers[towerDown]->_top->_width;
		int upWidth = _towers[towerUp]->_base->_width;
		int upLength = _towers[towerUp]->_base->_length;
		if( ! ((upLength<= downWidth && upWidth<=downLength)
				||((upLength<=downLength && upWidth<=downWidth))) ){
			return FAILURE;
		}
		int toDeleteTower;
		if(_towers[towerDown]->_size < _towers[towerUp]->_size){
			_towers[towerUp]->_root->_relativeHight += _towers[towerDown]->_size;
			_towers[towerDown]->_root->_relativeHight -= _towers[towerUp]->_root->_relativeHight;
			_towers[towerDown]->_root->_parent=_towers[towerUp]->_root->_position;
			_towers[towerUp]->_size += _towers[towerDown]->_size;
			_towers[towerUp]->_base = _towers[towerDown]->_base;
			_towers[towerDown]->_root->_tower=-1;
			toDeleteTower = towerDown;
		}else{
			_towers[towerUp]->_root->_relativeHight += _towers[towerDown]->_size;
			_towers[towerUp]->_root->_parent=_towers[towerDown]->_root->_position;
			_towers[towerDown]->_size += _towers[towerUp]->_size;
			_towers[towerDown]->_top = _towers[towerUp]->_top;
			_towers[towerUp]->_root->_tower=-1;
			toDeleteTower = towerUp;
		}
		delete _towers[toDeleteTower];
		_towers.current--;
		if(toDeleteTower==_towers.current){
			_towers.edit(_towers.current,NULL);
			return	SUCCESS;
		}
		_towers.edit(toDeleteTower,_towers[_towers.current]);
		_towers.edit(_towers.current,NULL);
		_towers[toDeleteTower]->_root->_tower=toDeleteTower;
		return SUCCESS;
	}

	StatusType towerHeight(int cube, int* height){
		if(cube<0 || height==NULL) return INVALID_INPUT;
		int tower=find(cube,NULL);
		if(tower==-1) return FAILURE;
		*height=_towers[tower]->_size;
		return SUCCESS;
	}
	StatusType HeightFromGround(int cube, int* height){
		if(cube<0 || height==NULL) return INVALID_INPUT;
		if(_pieces[cube]==NULL) return FAILURE;
		find(cube,height);
		return SUCCESS;
	}


};


int main(){
	Lego lego;
	int h1,h2;
	lego.addCube(4,5);
	std::cout<<lego._pieces.current<<" "<<lego._towers.current; // 1 1
	lego.addCube(7,7);
	lego.addCube(6,8);
	std::cout<<std::endl<<lego._pieces.current<<" "<<lego._towers.current; // 3 3
	std::cout<<std::endl<<lego._pieces[0]->_length<<" "<<lego._pieces[0]->_width <<
			" "<<lego._pieces[0]->_parent; //4 5 -1
	std::cout<<std::endl<<lego._pieces[1]->_length<<" "<<lego._pieces[1]->_width <<
				" "<<lego._pieces[1]->_relativeHight; //7 7 0
	std::cout<<std::endl<<lego._pieces[2]->_length<<" "<<lego._pieces[2]->_width <<
				" "<<lego._pieces[2]->_relativeHight; //6 8 0
	std::cout<<std::endl<<lego._pieces[2]->_tower<<" == 2"<<std::endl;
	std::cout<<std::endl<<lego._pieces[0]->_tower<<" == 0";

	lego.addCube(2,3);
	lego.addCube(3,2);
	lego.addCube(9,6);
	std::cout<<std::endl<<lego.putOnTop(1,7); //-1  wrong dimensions
	std::cout<<std::endl<<lego.putOnTop(-1,7); //-3  wrong input
	std::cout<<std::endl<<lego.putOnTop(0,-7); //-3  wrong input
	std::cout<<std::endl<<lego.putOnTop(0,0); //-1   same tower
	std::cout<<std::endl<<lego.putOnTop(2,2); //-1   same tower
	std::cout<<std::endl<<lego.putOnTop(1,2);//-1  wrong dimensions
	std::cout<<std::endl<<lego.putOnTop(2,1); //-1  wrong dimensions
	std::cout<<std::endl<<lego.putOnTop(5,1); //-1  wrong dimensions
	std::cout<<std::endl<<lego.putOnTop(4,3); //0    success
	std::cout<<std::endl<<lego._towers.current; //5
	std::cout<<std::endl<<lego.find(4,NULL)<<" == "<<lego.find(3,NULL); // 3 == 3
	std::cout<<std::endl<<lego._towers[3]->_size; //2
	std::cout<<std::endl<<lego.putOnTop(0,3); //-1
	std::cout<<std::endl<<lego.find(5,NULL); //4
	lego.addCube(2,2);
	std::cout<<std::endl<<lego.find(6,NULL); //5
	std::cout<<std::endl<<lego._towers.current; //6
	std::cout<<std::endl<<lego.putOnTop(6,3);//0
	std::cout<<std::endl<<lego.find(4,NULL)<<" == "<<lego.find(3,NULL)<<" == "<<lego.find(6,NULL); // 3 == 3 == 3
	std::cout<<std::endl<<" top tower 3 size: "<<lego._towers[3]->_top->_length<<" , "<<lego._towers[3]->_top->_width;// 2 , 2
	std::cout<<std::endl<<lego._towers[3]->_size; //3
	std::cout<<std::endl<<lego._towers.current; //5
	std::cout<<std::endl<<lego._towers[4]->_base->_position;//5
	std::cout<<std::endl<<lego.putOnTop(0,1);//0
	std::cout<<std::endl<<lego._towers.current; //4
	std::cout<<std::endl<<lego._towers[0]->_base->_position;//5
	std::cout<<std::endl<<lego.putOnTop(0,6); //-1  wrong dimensions
	std::cout<<std::endl<<lego.putOnTop(0,3); //-1  wrong dimensions
	std::cout<<std::endl<<lego.putOnTop(1,4); //-1  wrong dimensions
	std::cout<<std::endl<<lego.putOnTop(1,6); //-1  wrong dimensions
	std::cout<<std::endl<<lego.putOnTop(4,6); //-1  same tower
	std::cout<<std::endl<<lego.putOnTop(6,0); //0 success
	std::cout<<std::endl<<lego.putOnTop(6,0); //-1  same tower
	std::cout<<std::endl<<lego._towers.current; //3
	std::cout<<std::endl<<lego.find(4,NULL);//1
	std::cout<<std::endl<<lego.find(5,NULL);//0
	std::cout<<std::endl<<lego.find(2,NULL);//2
	lego.towerHeight(1,&h1);lego.towerHeight(6,&h2);
	std::cout<<std::endl<<lego._towers[1]->_size<<" == "<<h1<<" == "<<h2; //5 == 5 == 5
	lego.find(6,&h1); lego.find(4,&h2); std::cout<<std::endl<<h1<<" "<<h2<<" "; // 4 3 2 1 0
	lego.find(3,&h1); lego.find(0,&h2); std::cout<<h1<<" "<<h2<<" ";
	lego.find(1,&h1); std::cout<<h1<<" ";


	return 0;
}

